//
//  QuickSort.hpp
//  GraphC++
//
//  Created by Francesco De Martino on 30/11/12.
//  Copyright (c) 2012 Francesco De Martino. All rights reserved.
//

#ifndef GraphC___QuickSort_hpp
#define GraphC___QuickSort_hpp
#include "Sorter.h"
#include <iostream>

template <class T> class QuickSort : public Sorter<T> {
public:
    void sortVector(std::vector<T>* vector);
private:
    void quickSort(std::vector<T>* vector, int start, int end);
    int partition(std::vector<T>* vector, int start, int end);
    void swap(T *a, T *b);
};

template <class T> void QuickSort<T>::sortVector(std::vector<T>* vector) {
    quickSort(vector, 0, vector->size() - 1);

}

template <class T> void QuickSort<T>::quickSort(std::vector<T>* vector, int start, int end) {
    if (start < end) {
        int pivot = partition(vector, start, end);
        quickSort(vector, start, pivot - 1);
        quickSort(vector, pivot + 1, end);
    }
}

template <class T> int QuickSort<T>::partition(std::vector<T>* vector, int start, int end) {
    T pivot = vector->at(start);
    int j = start;

    for (int i = start + 1; i <= end; i++) {
        if (*(vector->at(i)) <  *pivot)
            swap(&(vector->at(i)), &(vector->at(++j)));
    }

    if (j != start)
        swap(&(vector->at(j)), &(vector->at(start)));

    return j;
}

template <class T> void QuickSort<T>::swap(T *a, T *b) {
    T tmp = *a;
    *a = *b;
    *b = tmp;
}

#endif
